1674D - A-B-C Sort - CodeForces Solution

constructive algorithms implementation sortings *1200

Please click on ads to support us..

Python Code: 

for _ in range(int(input())):
    
    n=int(input())
    l=list(map(int,input().split()))


    b=[0]*n  

    ans=[]

    if n&1:
        cnt=n  
        b[n//2]=l[0]
        i=(n//2)-1
        j=(n//2)+1

        k=1
        

        while cnt>0 and k<n:

            b[i]=l[k]
            b[j]=l[k+1]
            i-=1
            j+=1

            k+=2
            cnt-=1


        cnt=n 
        i=(n//2)-1
        j=(n//2)+1

        while cnt>0:

            if cnt&1:
                ans.append(b[cnt//2])

                cnt-=1

            else:
                ans.append(min(b[i],b[j]))
                ans.append(max(b[i],b[j]))
                i-=1
                j+=1
                cnt-=2

            

    else:
        cnt=n 
        i=n//2
        j=i-1
        k=0
        while cnt>0 and k<n:
            b[i]=l[k]
            b[j]=l[k+1]
            i+=1
            j-=1
            k+=2
            cnt-=1

            
        cnt=n 
        i=(n//2)
        j=(n//2)-1

        while cnt>0:
            ans.append(min(b[i],b[j]))
            ans.append(max(b[i],b[j]))

            i+=1
            j-=1
            cnt-=2


    for i in range(1,len(ans)):
        if ans[i]<ans[i-1]:
            print("NO")
            break

    else:
        print("YES")

C++ Code: 

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int TC;
    cin >> TC;
    while (TC--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }

        vector<int> res;
        if (n % 2 == 1) {
            res.push_back(a[0]);
            for (int i = 1; i < n; i += 2) {
                if (a[i] < a[i + 1]) {
                    res.push_back(a[i]);
                    res.push_back(a[i + 1]);
                } else {
                    res.push_back(a[i + 1]);
                    res.push_back(a[i]);
                }
            }
        } else {
            for (int i = 0; i < n; i += 2) {
                if (a[i] < a[i + 1]) {
                    res.push_back(a[i]);
                    res.push_back(a[i + 1]);
                } else {
                    res.push_back(a[i + 1]);
                    res.push_back(a[i]);
                }
            }

        }

        bool ok = true;
        for (int i = 1; i < n; i++) {
            if (res[i - 1] > res[i]) {
                ok = false;
                break;
            }
        }

        cout << (ok ? "YES" : "NO") << '\n';
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1180A - Alex and a Rhombus
445A - DZY Loves Chessboard
1372A - Omkar and Completion
159D - Palindrome pairs
981B - Businessmen Problems
1668A - Direction Change
1667B - Optimal Partition
1668B - Social Distance
88B - Keyboard
580B - Kefa and Company
960A - Check the string
1220A - Cards
897A - Scarborough Fair
1433B - Yet Another Bookshelf
1283B - Candies Division
1451B - Non-Substring Subsequence
1408B - Arrays Sum
1430A - Number of Apartments
1475A - Odd Divisor
1454B - Unique Bid Auction
978C - Letters
501B - Misha and Changing Handles
1496A - Split it
1666L - Labyrinth
1294B - Collecting Packages
1642B - Power Walking
1424M - Ancient Language
600C - Make Palindrome
1669D - Colorful Stamp
1669B - Triple